package com.leetcode.No0856;

import org.junit.Test;

/**
 * @program: Solution
 * @description: 括号的分数
 * 分治，递归
 * @author: Wang Zhihua
 * @date: 2022-10-09
 */
public class Solution2 {

    public int scoreOfParentheses(String s) {
        if (s.length() == 2) {
            return 1;
        }
        int bal = 0, n = s.length(), len = 0;
        for (int i = 0; i < n; ++i) {
            bal += (s.charAt(i) == '(' ? 1 : -1);
            if (bal == 0) {
                len = i + 1;
                break;
            }
        }
        if (len == n) {
            return 2 * scoreOfParentheses(s.substring(1, n - 1));
        } else {
            return scoreOfParentheses(s.substring(0, len)) + scoreOfParentheses(s.substring(len));
        }
    }

    @Test
    public void test1() {
        String s = "()";
        System.out.println(scoreOfParentheses(s));

        s = "(())";
        System.out.println(scoreOfParentheses(s));

        s = "()()";
        System.out.println(scoreOfParentheses(s));

        s = "(()(()))";
        System.out.println(scoreOfParentheses(s));

        s = "((()))()";
        System.out.println(scoreOfParentheses(s));

        s = "((())())";
        System.out.println(scoreOfParentheses(s));
    }
}
